The present invention relates to a computer system in which program execution is distributed across several machines. In particular, the present invention relates to a distributed computer system which utilises simulation information which influences the behaviour of program components being executed within the execution environment of the system.
It is known for a computer program to be divided up into a plurality of program components, e.g. program objects (for example in the context of object oriented software programming techniques) or computations, so that several components can be executed in parallel or so that one or more components can be executed in turn. A program component, such as a program object, can be considered to be a discrete item forming part of a computer program comprising data and procedures necessary to operate on that data.
Many techniques have been proposed which facilitate the interaction between multiple machines, at different locations, within the domain of a computer program via a network (e.g. a local area network (LAN) or the internet). In the context of computer games, for example, there is a desire for users to share a virtual world and to interact with each other, within that virtual world, in real-time.
Distributed or parallel execution of a computer program across several machines is problematic for a number of reasons. One of the main problems to be dealt with in implementing a distributed computer program is that, given the same user inputs, the execution of the same section of code on two different machines will tend to produce different results. This is primarily due to differences in the local hardware and software properties of those machines and also due to the machines executing sections of code at different speeds. Thus, distributed programming systems are often said to be non-deterministic, meaning that the outcome of executing the program cannot be predicted.
One of the main sources of non-determinacy within a distributed computer system arises as a result of locally derived input information. For example, many computer games utilise simulation information in the form of physics-based calculations in order to apply the laws of physics to program components populating the virtual environment and thereby improve the simulated realism of the game. Other types of simulation information may include information defining behaviour e.g. actions controlled by a script that is triggered at certain times or in certain circumstances or an algorithm generating behaviour on the fly. A third form of simulation information relates to user controlled behaviour e.g. the interactions of one or more user characters with the simulated world.
Physics simulation may result in a non-player character (NPC) standing around, held on the ground by gravity. Scripted or algorithmic behaviour can make the NPC character move e.g. by walking or turning. Physics simulation can then additionally be used to make realistic movements.
A third form of simulation information relates to user controlled behaviour e.g. the interactions of one or more user characters with the simulated world.
The required simulation information is typically derived using locally provided hardware components, or by software modules running on one or more processors installed on the local machine. For example, computer programs called “physics engines” are known which supply the computer game with values to define the movement and interactions of components within the virtual world. Similarly, hardware components, such as so-called physics accelerator cards, are also used in order to provide the data necessary to realistically simulate component motions in a way that models the laws of physics.
As a result of differing simulation systems generating simulation data to different levels of precision and with different rounding or floating point units, the use of simulation information during execution of a computer program will introduce the potential for a divergence between corresponding component states on different machines. Inconsistencies between the execution, and thus the simulation, of component interactions and behaviour between different machines comprised in a distributed system will quickly result in observably divergent behaviour. In some instances this divergence can even lead to different program results being obtained on different computers. Consider, for example, the case of a computer game which is operable to simulate an explosion within the virtual game world, wherein the explosion causes a plurality of the bricks to fly through the air colliding with each other and other components in the game. If different simulation information is used by different computers, it is possible for a character simulated on one computer to avoid being struck by one of the bricks and to live, but for the same character simulated on another computer to be struck by a brick and die.
To ensure that the behaviour, or execution, of an object (or any other computation) executed on one machine is the same as the behaviour of the corresponding object on another machine, it is necessary to ensure that the simulation information utilised during execution of the corresponding objects is derived from the same source.
In a computer system comprising a server and a plurality of clients, it is known for simulation information required by components executed within the system in a distributed fashion to be derived at a server, and for this information to be communicated to the client machines for their use in executing component execution. Alternatively, it is known for execution of a component to be conducted on the server and for details about the state of that component to be transmitted to the client.
However, these techniques utilise a significant amount of the bandwidth capacity available to the system to be taken up by transmissions operable to communicate the required simulation information to the various client components or the details of about the state of the corresponding component following execution on the server. Moreover, many computer systems support the execution of a large number of interacting components; these systems therefore require a substantial amount of simulation information to be derived in order that components behave in a realistic way. The quantity of information to be transmitted between machines via the network may be prohibitive, especially for global MMOGs (Massively Multiplayer Online Games). Indeed, as a result of bandwidth constraints, the implementation of distributed multiplayer games which use a high number of components requiring simulation information is often restricted to interaction over a local area network because they demand too much bandwidth resource to be properly implemented over the internet.
There is a therefore a need to reduce the bandwidth requirements of computer systems which comprise a distributed execution environment whilst alleviating the potential for divergence in the state of corresponding components being executed on different machines.
According to a first aspect of the present invention, there is provided a computer system comprising a program execution environment which is distributed between a server execution environment of a server apparatus and a client execution environment of a client apparatus, said client execution environment being operable to execute a plurality of client components, and said server execution environment being operable to execute a server component corresponding to each client component, wherein at least one client component is selected to be a primary client component, the or each primary client component being operable such that its execution, e.g. its behaviour and/or state, is influenced by simulation information which is derived from the same source as simulation information which is operable to influence the execution of the corresponding server component, and wherein a client component is selected to be a primary client component in dependence on a property of an instance of program execution in the client execution environment.
It should be appreciated that the behaviour of a component could be effected without a permanent change to the state of the component, i.e. it receives, uses and discards simulation information without altering its own state. Alternatively, the component could merely update its own state without visibly altering its external behaviour i.e. it could simply store details of simulation information for later potential use.
Preferably, the program execution environment comprises a deterministic execution environment.
According to one embodiment, simulation information derived for a server component that corresponds to a primary client component is communicated to both the primary client component and the corresponding server component, wherein said primary client component and said corresponding server component are operable, following receipt of said simulation information, to be executed using said simulation information. Thus, according to this embodiment, where a selected client component and corresponding server component require the input of simulation information in order to be executed to a future state, both components are operable to conduct the execution independently without introducing divergent behaviour as a result of using the simulation information.
Alternatively, simulation information derived for a server component that corresponds to a primary client component is communicated to the server component, said server component being operable, following receipt of said simulation information, to be executed using said simulation information to give an execution result, and wherein information relating to said execution result is communicated to the primary client component to which said server component corresponds.
A property of an instance of program execution in the client execution environment may be, for example, related to a measure of the “importance” of the simulation or execution of that component by the client machine. The level of importance of a component will generally be from the perspective of the program user, the player, or virtual player (character) as displayed on the display means of the client machine. In other words, how important the simulation of that component is to the realism, virtual properties, or outcome of running the program. Thus, according to embodiments of the present invention, the selection of primary client components is client dependent. For example, a primary client component may be selected in dependence upon a measure of the apparent distance to said component when simulated on said display means of said client. Thus, client components may be classified into foreground components and background components, wherein the execution environment is operable to allow the execution of the foreground components to behave in the same way as the corresponding server component. Thus, according to this embodiment, the behaviour of the foreground components and the corresponding components on the server is governed by simulation information that is derived from the same source.
Where a client component other than a selected client component requires simulation information in order to be executed to a future state, this information may be derived locally, for example by means of a simulation system such as a locally implemented physics engine or a locally implemented physics accelerator. Thus, the state of these components will be different to the state of the corresponding server components which will have been executed using simulation data generated by a simulation system of the server.
Regarding such physics engines and physics accelerators, it is envisaged that add-on hardware cards may be utilised in a widespread fashion for gaming which is demanding, both in graphics and computation. In the same way that existing hardware systems utilise powerful graphics processor units (GPUs) on graphics cards, it is envisaged that additional hardware may be employed to enable complex physics calculations to be taken away from the main motherboard processor.
Preferably, the server periodically transmits correction information for a destination client component that is not a primary client component. Preferably, the correction information comprises information about the state of the server component corresponding to said destination client component. Preferably, the server is operable to transmit correction information to the or each client comprised in the system. Following receipt of this correction information, a client apparatus is operable to change the state of one or more of its components which are not primary client components based on said correction information.
Thus, according to preferred embodiments of the present invention, the execution environment operates to ensure that a subset of client components will behave in the same way as the corresponding server component(s). This means that the state of the selected primary client component will be the same as the state of the corresponding server component at a given point in the execution of the component code.
This is achieved, according to embodiments of the present invention, by ensuring that the behaviour of corresponding components is influenced by simulation information that is derived from the same source.
According to a further aspect of the present invention, there is provided a server apparatus comprising a server execution environment, said server being for use in a computer system comprising a program execution environment which is distributed between said server execution environment and a client execution environment,                wherein said server is operable to execute a server component corresponding to each component operable to be executed within said client execution environment,                    and wherein said server is operable to communicate with a primary client component such that the behaviour and or state of said primary client component is influenced by simulation information which is derived from the same source as simulation information which influences the behaviour and or state of the server component corresponding to said primary client component, wherein said primary client component has been selected in dependence on a property of an instance of program execution in the client execution environment.                        
According to a still further aspect of the present invention there is provided a client apparatus comprising a client execution environment, said client being for use in a computer system comprising a program execution environment which is distributed between a server execution environment and said client execution environment,                said client execution environment being operable to execute a plurality of client components,        wherein at least one client component is selected to be a primary client component in dependence on a property of an instance of program execution in the client execution environment, the or each primary client component being operable to communicate with said server such that its behaviour and/or state is influenced by simulation information derived from the same source as simulation information which influences the behaviour and/or state of a server component operable to be executed by said server execution environment and corresponding to said primary client component.        
According to embodiments of the present invention the client execution environment may execute one or more components for simulation on a display means thereof, or to generate an auditory effect. It will be appreciated that there may be components executing within the client execution environment which do not have a representation on a display, for example, if a single component is implemented as a collection of executing components.
Advantageously, embodiments of the present invention are capable of supporting the execution of large numbers of program components executing within a distributed execution environment, whilst permitting a reduction in the bandwidth requirements of the system and also improving overall system responsiveness. Essentially, embodiments of the present invention ensure that those components that are considered to be important from the perspective of each client comprised in the system, according to some defined heuristic or algorithm, are simulated to a high degree of accuracy with respect to the simulation results obtained on the server. Furthermore, embodiments of the present invention provide a way of handling divergent behaviour of the less important client components with efficient use of bandwidth capacity.
Embodiments of the present invention are particularly advantageous in that they facilitate an efficient use of the bandwidth capacity available to a distributed system whilst still enabling all components to be simulated within the virtual world with a high degree of realism.
In United Kingdom Patent Application No. 0712496.9 (hereinafter “GB 0712496.9”), and its counterpart U.S. application Ser. No. 11/773,304, the entire content of which is incorporated herein by way of reference thereto, a computer system is proposed comprising an execution environment which is structured to facilitate execution of code in “frames”, or units of time, with at least one program component, e.g. program “object”, comprised in each frame.
According to the rules of the system described in GB 0712496.9, components are allowed to communicate with components in another frame but communication is not possible between components in the same frame. For each frame, the system runs through all the components in the system and executes each one. Components may be executed out of order or in parallel. Each component has a state that includes a fixed amount of data for the component and an execution point. When a component is created, the execution point is at the start of the component's main procedure. When execution of the component's main procedure reaches a next-frame statement, then execution of that component stops for this frame. At the end of the frame, the new component state is stored. During execution of a component's code, messages may be created. These must be queued up and attached to a target component. Messages can only be read by the target component on the next frame. The messages may also need to be transmitted over a network. Also, a component might read in messages. The messages must be read in a deterministic order. This is to allow out-of order and parallel execution on multiple systems. The order can be defined by the system. At the end of the frame all unused messages can be discarded. All modified components are modified and the frame number is increased by 1. Execution can continue onto the next frame.
Before executing the code of a component it is necessary to know that (for this frame) all potential messages from any component in the system (i.e. across the entire network), or the state of other components that this component refers to must be available. If not, it might be desirable to execute speculatively. For example, the component and its frame number may be stored and then the execution can continue without all of the information required. The component may be marked as speculative so that it may be possible to revisit this component and re-execute it “correctly” once all of the required information has arrived.
FIG. 1 shows the execution of four objects, labelled a to d, according to the distributed computer system described in GB 0712496.9. The state in frame n is known and execution of frame n has produced a message from b to a. In frame n+1, object c reads data from objects b and d. In frame n+2, object a reads data from object c. From FIG. 1, it can be seen that there is no communication between objects in the same frame. Message dependencies only exist from one frame to the next, while read dependencies only exist from the current frame to the previous frame. This feature is what allows the system to be executed in parallel and over a network. The diagram shows a partial execution in which a is calculated up to frame n+1 and b is ignored. This is to illustrate that it is possible to execute beyond the current consistent network state to calculate a speculative state (which will be based on a mixture of real input data and guessed input data). However, if it is later discovered that b in frame n+1 sends a message to a then, the execution of a in frame n+1 is potentially false and may need to be re-calculated.
The code for each object for each frame can be considered as a function of the value of all the referenced objects in the previous frame and all the messages received by the object. Therefore, if the objects in frame n and the messages from frame n to frame n+1 are consistent throughout the system, then the state of all objects in frame n+1 and the messages from frame n+1 to frame n+2 are just a function of data that is consistent throughout the system. Therefore, the objects will stay consistent as long as the initial state and initial messages are consistent and the functions are executed consistently. In other words, the system is deterministic because all of its causes are known.
Thus, the computer system described in GB 0712496.9 may be advantageous in a distributed implementation since it facilitates the deterministic execution of a computer program ensuring that if the same component in the same state executes the same code on two different computers, or at two different times, then the new state of the component will be identical on both machines or at both times.
According to a preferred embodiment of the present invention, the execution of program components is conducted in accordance with the techniques described in GB 0613275.7, from which U.S. application Ser. No. 11/773,304 claims priority. Accordingly, a program execution environment is provided which is operable such that the execution of one or more components of a computer program is carried out in a plurality of sequential frames of execution, wherein the execution environment is further operable to:    i) allow communication between one said component and another said component in different frames of execution; and    ii) to prevent communication between one said component and another said component in the same frame of execution
The communication between components may include at least one of sending a message or reading at least a portion of the state of another component. The communication may take place between components of adjacent frames or between components of frames which are more than one frame apart. Preferably, the execution environment is operable to process messages in a pre-determined order. The component may consist of an object (i.e. a discrete item forming part of a computer program comprising data and procedures necessary to operate on that data).
An execution environment according to GB 0712496.9 is advantageously structured to facilitate execution of program code in “frames”, i.e. or units of time or work, with at least one component of the program, comprised in each frame of execution. Moreover, if corresponding objects (i.e. —a discrete program component, for example implementing a character in a game, that is executed on two different machines) in the same state execute the same code on two different computers, or at two different times, then the new state of the object will advantageously be identical on both machines or at both times. Such an execution environment will be particularly advantageous in a distributed implementation since it facilitates the execution of a computer component in a distributed environment with a high degree of determinism. Dividing the program into sequential frames also advantageously allows different program components, or different objects, to be executed in parallel. Thus, the execution of multiple program portions may occur in parallel in any given frame.
According to the teaching described in GB 0712496.9, program components are executed in frames wherein a component in one frame is able to communicate with a component in a different, e.g. adjacent, frame but communication is not possible between components in the same frame. On the server, the server execution environment is operable to allow all communications to proceed between the server components. The server components are also operable to receive outside world messages and communication from a data generation unit. Thus, the state of any component to be executed on the server will be deterministic and will be a function of all communication to that component, including any simulation information that is communicated to the server object from a data generation unit. It is possible for simulation information to be communicated to a component by way of messages sent to the component, or by a component reading data from a data generation unit.
On the client, however, since non-primary client components will be receiving simulation information from a source different to that of the corresponding server component, it is undesirable to allow non-primary client components to communicate with primary client components since this will introduce the potential for a divergence in the state of a primary client component and its corresponding server component.
According to a particularly preferred embodiment of the present invention, the computer system is operable to ensure that the behaviour of a primary client component will tend to duplicate the behaviour of the corresponding server component. Preferably, the client component will behave in exactly the same way as the corresponding server component. Effectively, this means that the primary client components become a “subset” of the corresponding server client set, in that the execution of the subset mirrors the execution of the corresponding server set.
This is achieved, according to one embodiment, by the system being operable to ensure that any communications to a server component corresponding to a primary client component are also communicated to the primary client component. Thus, if information is to be communicated to a primary client component from a non-primary client component, the execution environment is operable to allow this communication to take place from the server component corresponding to the non-primary client component. Similarly, if a primary client component needs to read information from a non-primary client component, the execution is operable to allow this to be from the server component corresponding to the non-primary client component.
Advantageously, in accordance with this embodiment, the execution of primary client components is also deterministic and will be “correct” in the sense that that it will duplicate the execution of the corresponding server components and will be influenced by simulation information that as been derived from one source.
Alternatively, according to an embodiment of the present invention, the behaviour of a primary client component will be made to duplicate the behaviour of the corresponding server component by performing execution of the corresponding server component code and then transmitting details of the execution result to the primary client component.
The most appropriate mechanism for facilitating the duplication of server component states to a corresponding primary client component is chosen having regard to the quantity of information to be transmitted via the network. Thus, in some circumstances, it may be more efficient (in terms of bandwidth capacity) to send communications to the primary client component in order that the primary client components are operable to execute independently, but in a deterministic fashion. In other circumstances, it will be more efficient to transmit details of the result of execution performed on the server.
The system may be provided with another type of component, namely a “simulation component”, e.g. a “simulation object” which may, for example, be a “physics object”. This is useful if, for example, a non-deterministic simulation system is being used i.e. a simulation system whose output data has the potential to give non-deterministic results whose accuracy is adversely affected by external factors such as timing and order of execution. The simulation component is operable to receive simulation information from a simulation data generation unit and to derive component specific simulation information for affected components.
A simulation component, which may be provided within the server execution environment and/or the client execution environment, is operable to calculate any simulation data needed by various affected program components and to communicate this information to those components. Thus, according to embodiments of the present invention, the simulation component on the server is operable to communicate simulation information to the primary client components whilst the simulation component on the client will control non-primary client components.
Within the context of the present invention, the simulation component (which might be implemented as part of a C++ system, rather than within the rules of an execution environment which is operating in frames, as described above), behaves differently depending on whether the current frame is being executed speculatively (i.e. ahead of the server) or consistently (i.e. in-step with the server).
When the client execution environment is operating speculatively, the client's simulation component may be used to control both primary and non-primary components. These components can later be corrected by means of correction data sent from the server.
In any of the above aspects or embodiments, the various features may be implemented in hardware, or as software modules running on one or more processors. Features of one aspect or embodiment may be applied to any of the other aspects or embodiments.
The invention also provides a computer program or a computer program product for implementing the techniques described herein, and a computer readable storage medium having stored thereon a program for implementing the techniques described herein. A computer program embodying the present invention may be stored on a computer-readable medium, or it could, for example, be in the form of signal such as a downloadable data signal provide from an internet website, or it could be in any other form.
For a better understanding of the present invention, and to show how the same may be carried into effect, reference will now be made, by way of example, to the accompanying drawings in which: